#include <bits/stdc++.h> 
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        int words_Num = words.size();
        int word_Len = words[0].length();
        int sLen = s.length();
        for(int left=0; left<word_Len; ++left){
            int right = left+words_Num*word_Len;
            unordered_map<string, int> mp;
            if(right > sLen) break;
            // unordered_map<string, int> mp;
            for(int i=left; i<right; i+=word_Len){
                mp[s.substr(i, word_Len)]++;
            }
            for(auto& word: words){
                --mp[word];
                if(mp[word] == 0) mp.erase(word);
            }
            if(mp.empty()) ans.push_back(left);
            //注意是<=
            for(int i=left, j=right; j+word_Len<=sLen; j+=word_Len, i+=word_Len){
                string strFront = s.substr(i, word_Len);
                string strAfter = s.substr(j, word_Len);
                if(--mp[strFront] == 0) mp.erase(strFront);
                if(++mp[strAfter] == 0) mp.erase(strAfter);
                if(mp.empty()) ans.push_back(i+word_Len);
            }
        }
        return ans;
    }
};


int main(){

}